<?php
/**
 * zen_algoritmos.php
 * @author Juan Belon
 * @access public
 * @copyright LGPL, GPL
 * @package zenphp
 * @version 0.1.1
 * @uses zenphp FrameWork
 * @link http://csl2-zenphp.forja.rediris.es
 * @link http://www.zenphp.es
 * @link https://forja.rediris.es/projects/csl2-zenphp/
 * @brief Funciones para ordenar matrices y otros algoritmos básicos de la programación y la Teoria de Algoritmos. ;)
 */
if (!defined('ZF_SEGURO_ZEN')) die(_("No se puede acceder aqui sin mas ;)"));
// +----------------------------------------------------------------------
// | zenphp.es
// +----------------------------------------------------------------------
/**
* Define la constante del umbral para el algoritmo QuickSort
*/
define('ZF_ORDENA_UMBRAL_QS',50);
/**
 * Ordena parte de un vector por el método de inserción.

   @param array $T : vector de elementos. Tiene un número de elementos 
                   mayor o igual a final. Es MODIFICADO.
   @param int $inicial : Posición que marca el incio de la parte del
                   vector a ordenar.
   @param int $final : Posición detrás de la ultima de la parte del
                   vector a ordenar. 
		   $inicial < $final.

   Cambia el orden de los elementos de T entre las posiciones
   inicial y final - 1 de forma que los dispone en sentido creciente
   de menor a mayor.
   Aplica el algoritmo de inserción.
 */
function zen_ordena_insercion_lims(&$T, $inicial, $final)
{  
  for ($i = $inicial + 1; $i < $final; $i++) {
    $j = $i;
    while (($T[$j] < $T[$j-1]) && ($j > 0)) {
      $aux = $T[$j];
      $T[$j] = $T[$j-1];
      $T[$j-1] = $aux;
      $j--;
    };
  };
}

/**
* Funcion para ordenar un array $T de $num_elem elementos con el 
* algoritmo de ordenacion QuickSort
* @param array $T
* @param int $num_elem
*/
function zen_ordena_quicksort(&$T,$num_elem)
{
  zen_ordena_quicksort_lims($T, 0, $num_elem);
}
/**
* Algoritmo recursivo QuickSort
* @param array $T 
* @param int $inicial
* @param int $final
*/
function zen_ordena_quicksort_lims(&$T, $inicial, $final)
{
  if ($final - $inicial < ZF_ORDENA_UMBRAL_QS) {
    zen_ordena_insercion_lims($T, $inicial, $final);
  } else {
  	$k = null;
    zen_ordena_dividir_qs($T, $inicial, $final, $k);
    zen_ordena_quicksort_lims($T, $inicial, $k);
    zen_ordena_quicksort_lims($T, $k + 1, $final);
  };
}

/**
 * Redistribuye los elementos de un vector segun un pivote.

   @param array $T : vector de elementos. Tiene un numero de elementos 
                   mayor o igual a final. Es MODIFICADO.
   @param int $inicial : Posicion que marca el incio de la parte del
                   vector a ordenar.
   @param int $final : Posicion detras de la ultima de la parte del
                   vector a ordenar. 
		   inicial < final.
   @param int $pp : Posicion del pivote. Es MODIFICADO.

   Selecciona un pivote los elementos de T situados en las posiciones
   entre inicial y final - 1. Redistribuye los elementos, situando los
   menores que el pivote a su izquierda, despues los iguales y a la
   derecha los mayores. La posicion del pivote se devuelve en pp.
 *
 */
function zen_ordena_dividir_qs(&$T,$inicial, $final, &$pp)
{
  $pivote = $T[$inicial];
  $k = $inicial;
  $l = $final;
  do {
    $k++;
  } while (($T[$k] <= $pivote) && ($k < $final-1));
  do {
    $l--;
  } while ($T[$l] > $pivote);
  while ($k < $l) {
    $aux = $T[$k];
    $T[$k] = $T[$l];
    $T[$l] = $aux;
    do $k++; while ($T[$k] <= $pivote);
    do $l--; while ($T[$l] > $pivote);
  };
  $aux = $T[$inicial];
  $T[$inicial] = $T[$l];
  $T[$l] = $aux;
  $pp = $l;
};
/**
 * Ordena un vector por el metodo de montones.

   @param array $T : vector de elementos. Debe tener num_elem elementos.
             Es MODIFICADO.
   @param int $num_elem : numero de elementos. num_elem > 0.

   Cambia el orden de los elementos de T de forma que los dispone
   en sentido creciente de menor a mayor.
   Aplica el algoritmo de ordenacion por montones.
 */
function zen_ordena_heapsort(&$T,$num_elem)
{
  
  for ($i = $num_elem/2; $i >= 0; $i--)
    zen_ordena_reajustar($T, $num_elem, i);
  for ($i = $num_elem - 1; $i >= 1; $i--)
    {
      $aux = $T[0];
      $T[0] = $T[$i];
      $T[$i] = $aux;
      reajustar($T, $i, 0);
    }
}
  
/**
   Reajusta parte de un vector para que sea un monton.

   @param array $T : vector de elementos. Debe tener num_elem elementos.
             Es MODIFICADO.
   @param int $num_elem : numero de elementos. num_elem > 0.
   @param int $k : indice del elemento que se toma com raiz
   
   Reajusta los elementos entre las posiciones k y num_elem - 1 
   de T para que cumpla la propiedad de un monton (APO), 
   considerando al elemento en la posicion k como la raiz.
 */
function zen_ordena_reajustar(&$T, $num_elem, $k)
{
  $v = $T[$k];
  $esAPO = false;
  while (($k < $num_elem/2) && !$esAPO)
    {
      $j = $k + $k + 1;
      if (($j < ($num_elem - 1)) && ($T[$j] < $T[$j+1])) $j++;
      if (v >= $T[$j]) $esAPO = true;
      $T[$k] = $T[$j];
      $k = $j;
    }
  $T[$k] = $v;
}
/**
 * Algoritmo de ordenacion de matrices MergeSort 
 * Deja reservas de memoria pendientes...¡Menos recomendable!
 *
 * @param array $a
 * @param int $izda
 * @param int $dcha
 * @return bool
 */
function zen_ordena_mergeSort(&$a,$izda=null,$dcha=null){
	if (!is_array($a)) return false;
	$n = sizeof($a);
	if ($izda==null || $izda>$n-1) $izda = 0;
	if ($dcha==null || $dcha>$n)   $dcha = $n;
	//Ordena $a[$izda:$dcha]
	if ($izda<$dcha){
		//al menos 2 elementos
		$mitad = ($izda+$dcha)/2; //punto medio
		$b1 = $b2 = null;		
		zen_copia_array($a,$b1,$izda,$mitad); //copia la primera parte
		zen_copia_array($a,$b2,$mitad+1,$dcha); //copia la segunda parte
		zen_ordena_mergeSort($b1,$izda,$mitad);
		zen_ordena_mergeSort($b2,$mitad+1,$dcha);
		zen_intercambiar_array($a,$b1,$b2,$izda,$mitad,$dcha); //combinar b1 y b2 en a
	} else return false;
}

/**
 * Copia un array en otro desde el inicio al destino
 *
 * @param array $origen
 * @param array $destino
 * @param array $inicio
 * @param array $fin
 * @return bool
 */
function zen_copia_array(&$origen,&$destino,$inicio,$fin){	
	if (!is_array($origen)) return false;
	$destino = array();
	$n = count($origen);
	for($i=$inicio; ($i<$n && $i<$fin); $i++) $destino[$i] = $origen[$i];
	return true;
}
/**
* Algoritmo de ordenacion por insercion
* @param array $T
* @param int $num_elem
*/
function  zen_ordena_insercion(&$T, $num_elem)
{
  zen_ordena_insercion_lims($T, 0, $num_elem);
}



?>
